import java.util.*;

/**
 * Created by zhourh on 2018/8/13.
 *
 * 我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。

 如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方；6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。

 现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？

 */
public class RotatedDigits {

    private static List<Integer> rotateNums = new ArrayList<>();
    private static List<Integer>  unRotateNums = new ArrayList<>();
    private static List<Integer> goodNumbers = new ArrayList<>();

    public static void main(String[] args) {
        System.out.println(new RotatedDigits().rotatedDigits(857));
        System.out.println(goodNumbers);
        System.out.println(new RotatedDigits().rotatedDigits(3));
        System.out.println(new RotatedDigits().rotatedDigits(10));
        System.out.println(new RotatedDigits().rotatedDigits(10));
    }

    static {
        rotateNums.add(2);
        rotateNums.add(5);
        rotateNums.add(6);
        rotateNums.add(9);

        unRotateNums.add(3);
        unRotateNums.add(4);
        unRotateNums.add(7);

        goodNumbers.add(2);
        goodNumbers.add(5);
    }


    public int rotatedDigits(int N) {
        if (N <= 1) {
            return 0;
        }


        int maxGoodNumber = goodNumbers.get(goodNumbers.size() - 1);

        if (N <= maxGoodNumber) {
            if (isGoodNumber(N)) {
                return goodNumbers.indexOf(N) + 1;
            }
            return rotatedDigits(N - 1);

        }

        for (int i = maxGoodNumber + 1; i <= N; i++) {
            if (isGoodNumber(i)) {
                goodNumbers.add(i);
            }
        }

        return goodNumbers.size();
    }

    private boolean isGoodNumber(int n) {
        List<Integer> nums = new ArrayList<>();
        while (n != 0) {
            nums.add((n % 10));
            n /= 10;
        }

        int rotateCount = 0;
        for (int num : nums) {
            if (rotateNums.contains(num)) {
                rotateCount++;
            } else if (unRotateNums.contains(num)) {
                return false;
            } else {
                continue;
            }
        }

        return rotateCount > 0;

    }
}
